1. Field of the Invention
The present invention relates, in general, to an encoder for a multiplier employing a Booth algorithm.
2. Description of the Related Art
Binary multiplication is an important function in many digital signal processing applications. Some applications further require arithmetically combining a product with the results of previous operations (e.g. forming a sum of products). A versatile multiplier circuit should have the capability to perform these functions in either a two's complement or an unsigned magnitude notation.
Binary numbers are multiplied very much like decimal numbers. More particularly, each digit of one operand (multiplicand) is multiplied by each digit of the other operand (multiplier) to form partial products and these resulting partial products are then added, taking into account the multiplier digit position place significance.
Circuits for multiplying binary numbers require a relatively large number of circuit elements and thus take up a fair amount of chip area when fabricated on an integrated circuit. For this reason, an ongoing goal of integrated circuit designers is to find ways to implement a multiplier circuit (‘multiplier’) with fewer and fewer circuit elements.
Conventional multipliers may include encoders, compressors, and adders. The encoders are blocks that encode multipliers and multiplicands and generate partial sums through multiplications of the multipliers and the multiplicands. The encoders in these multipliers may employ many known techniques for reducing the time required to perform a binary multiplication. For example, different encoding methods have been devised which reduce the number of partial products which must be added up to form the final product and for speeding up the addition of partial products. As an example, the encoders may employ a corrected Booth algorithm (also known as a modified Booth algorithm) to reduce the number of partial sums.
The modified Booth algorithm (hereafter ‘Booth algorithm’) is a multiplication method that enhances a multiplication speed by reducing the number of multiplications of the multipliers and the multiplicands having a plurality of bits during encoding. The algorithm encodes one of the two numbers being multiplied. This approach reduces, usually by a factor of two, the number of partial products generated by the multiplier, thereby reducing the amount of circuitry needed to combine the partial products in arriving at the final product.
FIG. 1A is a diagram illustrating an encoder cell of a conventional multiplier employing the Booth algorithm; and FIG. 1B is a diagram illustrating a partial-product cell of a conventional multiplier employing the booth algorithm. The conventional encoders of a multiplier employing the corrected or modified Booth algorithm may be comprised of encoder cells that generate operators using the multipliers and partial-product cells that encode the multiplicand using the operators. FIGS. 1A and 1B show only encoder cell and partial-product cell portions thereof, which would be part of a multiplier including adders and compressors, for example.
As shown in FIG. 1A, the conventional encoder cell 100 may include an exclusive logical sum gate XOR11, logical product gates AND11, AND12, a multiplexer MUX11, and buffers B11, B12, B13.
The encoder cell 100 encodes first to third multiplier data Y2j−1, Y2j, Y2j+1 and selectively outputs operators 1X, 2X, NEG. Each multiplier data Y2j−1, Y2j, Y2j+1 may be comprised of a plurality of bits, with Y2j−1, Y2j representing adjacent sets of bits, the bits of Y2j−1 being of lesser significance than the bits of Y2j. In an example, each of the first to third multiplier data Y2j−1, Y2j, Y2j+1 may represent three given places of bits of a multiplier Y input to the encoder cell 100. The output operator 1X indicates that a multiplicand X has been multiplied by 1, operator 2X indicates that the multiplicand X has been multiplied by 2, and the operator NEG indicates whether the multiplicand X is multiplied by a positive value or a negative value (i.e., the signs of the output operators 1X and 2X are determined by the operator NEG). The first to third multiplier data Y2j−1, Y2j, Y2j+1 and the operators 1X, 2X, NEG have relationships as shown in Table 1.
TABLE 1Truth Table of logic states for multipliers and operatorsY2j + 1Y2jY2j − 1OPERATORX2XNEG000  0X000001+1X100010+2X100011−2X010100−1X011101  0X101110101111001
Referring to FIG. 1B, the partial-product cell 110 shown in FIG. 1B may include inverted logical product gates NAND11, NAND12, NAND13 and an exclusive logical sum gate XOR12. The partial-product cell 110 selects output paths of the multiplicand data Xi, Xi−1 received in response to the operators 1X, 2X, NEG which are output from the encoder cell 100 to the partial-product cell 110, so as to output the selection results as partial-product data Pi, 2j. 
One of the problems facing conventional multipliers in general and the conventional encoder cells and partial-product cells in such multipliers is that there may be substantial delay in generating partial-product data for a multiplicand, making it difficult to achieve high-speed partial product generation. For example, as seen in FIGS. 1A and 1B, the conventional encoder of the conventional multiplier has a three-gate delay maximum including the buffers in the encoder cell 100 (see, for example, AND11, MUX11 and inverter B12 to output operator 2X) and a three-gate delay in the partial-product cell 110 (see, for example, NAND12, NAND13 and XOR12 to generate partial-product data Pi, 2j), so that the encoder has a total of a six-gate delay in order to generate partial-product data from the input multiplier data Y2j−1, Y2j, Y2j+1 and multiplicand data Xi, Xi−1 received in response to the operators 1X, 2X, NEG. As used herein, gate delay may refer to a signal delay as a signal passes through a transistor gate within a given component such as a MUX, one of an AND, NAND, OR, XOR gate, and/or a buffer/inverter component.
That is, the partial-product data Pi, 2j are output after the multiplier data Y2j−1, Y2j, Y2j+1 and the multiplicand data Xi, Xi−1 pass through the six gates (for example, AND11, MUX11, B12, NAND12, NAND13, and XOR12). This delay time may thus cause an undesirable reduction in operation speed of the multiplier.
Further, since the operator NEG having only a one-gate delay (buffer delay at B13) reaches the exclusive logical sum gate XOR12 (which represents an output terminal of the partial-product cell 110) prior to the other operators 1X, 2X reaching XOR12 (due to the three-gate delay), the exclusive logical sum gate XOR12 is turned on for an unnecessarily long duration, so that leakage currents could be generated regardless of generation of the partial-product data Pi, 2j. In other words, the operators NEG, 1X and 2X do not arrive at XOR12 at the same time.
Further, the conventional encoder has a relatively large number of pass transistors. Thus, the circuit scale for the encoder, and hence the multiplier is large and takes up a fair amount of chip area when fabricated on an integrated circuit.
FIG. 2A is a diagram illustrating the encoder cell of another conventional multiplier employing the Booth algorithm; and FIG. 2B is a diagram illustrating the partial-product cell of another conventional multiplier employing the Booth algorithm.
As shown in FIGS. 2A and 2B, encoder cell 200 may include an inverted exclusive logical sum gate XNOR21, a logical product gate AND21, a logical sum gate OR21, an inverted logical gate NAND21, an inverted logical sum gate NOR21, and inverters I21 to I27.
The encoder cell 200 encodes first to third multiplier data Y2j−1, Y2j, Y2j+1 of multiplier data having a plurality of bits, and selectively outputs operators 1X, 2X, PL, M (as shown in FIGS.2A and 2B, binary complements PLb and Mb of the operators PL and M (due to inversion at inventers I26 and I27) are output as operators from encoder cell 200. The first to third multiplier data Y2j−1, Y2j, Y2j+1 and the operators 1X, 2X, PL, M have relationships as shown in Table 2.
TABLE 2Truth Table of logic states for multipliers and operatorsY2j + 1Y2jY2j − 1OPERATORX2XPLM000  0X0100001+1X1010010+2X1010011−2X0110100−1X0101101  0X100111010011110100
Signs of the operators 1X, 2X in Table 2 may be determined by logic levels of the operators PL, M. PL indicates a positive sign, and M indicates a negative sign.
The partial-product cell 210 shown in FIG. 2B includes inverters I28 and I29 and multiplexers MUX21, MUX22, MUX23, MUX24. The partial-product cell 210 selects output paths of multiplicand data Xi, Xi−1 to be received in response to the operators 1X, 2X, PL, M output from the encoder cell 200, and outputs the selection results as partial-product data Pi, 2j, Pi−1,2j. 
The conventional encoder of FIGS. 2A and 2B has reduced delay time therein as compared to the encoder of FIGS. 1A and 1B. In the encoder shown in FIGS. 2A and 2B, an encoding process of the partial-product cell 210 is improved since fewer transistors are employed by using the operators PL, M. As shown in FIG. 2A, for the multiplier data Y2j−1, Y2j, the encoder cell 200 has a maximum of a three-gate delay (including the inverters) in order to generate operators 1X, 2X, PL and M, and the partial-product cell 210 has a maximum of a two-gate delay to generate partial-product data Pi, 2j, Pi−1,2j. 
Therefore, although some signal paths between the input multiplier data and the generated partial-product data Pi, 2j, Pi−1,2j may have less delay, at least one path in the encoder of FIGS. 2A and 2B has at least a five-gate delay in total. Thus, the encoder of FIGS. 2A and 2B has a total gate delay time that is shortened by one gate, as compared with the encoder of FIGS. 1A-1B. However, since the circuit construction of the encoder cell 200 is complicated due to the operators PL, M, and since the operators PL, M are delayed by at least one gate more than are the other operators 1X, 2X (i.e., the sign operators are generated later than the operators 1X, 2X), operation speed of a multiplier with the conventional encoder of FIGS. 2A and 2B may still be slowed.